Задача #A0037

Память 16 MB Время 500 ms Сложность 59 %

So’rovlarni tartiblash 2

Sizga N uzunlikdagi A massivi berilgan. Massiv ustida bajarish uchun Q ta so’rov berilgan. Har bir so’rov quyidagilardan biri bo’lishi mumkin:

L R X : Massivning [L, R] indekslari oralig’idagi barcha elementga X sonini qo’shish
L R X : Massivning [L, R] indekslari oralig’idagi barcha elementni qiymatini X ga almashtirish

Berilgan barcha so’rovlar massiv ustida bajarilishi kerak.

Sizga so’rovlarning bajarilish tartibini o’zgartirishga ruxsat etiladi. So’rovlar oxirida A massivning hosil qilish mumkin bo’lgan leksikografik eng katta qiymatini aniqlang.

Входные данные:

Kirish faylining dastlabki satrida ikkita butun son, N(1 ≤ N ≤ 10⁵) va Q(1 ≤ Q ≤ 10⁵) kiritiladi.

Ikkinchi satrda N ta butun son, A(-10⁵ ≤ A_i ≤ 10⁵) massiv elementlari kiritiladi.

Keyingi qatordan boshlab Q ta qatorda 4 tadan butun son, so’rov turi({1,2}), L, R(1 ≤ L ≤ R ≤ N), X(-10⁵ ≤ X ≤ 10⁵) kiritiladi.

Выходные данные:

Chiqish faylining yagona satrida N ta butun son, A massiv ustida barcha so’rovlarni bajargandan so’ng hosil qilish mumkin bo’lgan leksikografik eng katta massivni chop eting.

Примеры

#	input.txt	output.txt
1	5 3 1 2 3 4 5 1 3 4 2 2 1 2 3 1 4 5 -6	3 3 5 0 -1

Telegram Facebook

Отправить решение

Пожалуйста, войдите в систему, чтобы выполнить это действие,если у вас нет учетной записи, вы можете зарегистрироваться в любое время